Shapley values and functional decompositions

based on:
M. Hiabu, J. T. Meyer, M. N. Wright. Unifying local and global model explanations by functional decomposition of low dimensional structures. AISTATS 2023.

presented by:
Mateusz Krzyziński
supported by Hubert Baniecki

Paper(s)

Main: Munir Hiabu, Joseph T. Meyer, Marvin N. Wright. Unifying local and global model explanations by functional decomposition of low dimensional structures.
Side: Sebastian Bordt, Ulrike von Luxburg. From Shapley Values to Generalized Additive Models and back.

Both accepted at International Conference on Artificial Intelligence and Statistics (AISTATS) 2023.

Motivating example

Misleading SHAP values

Consider the function \[m(x_1, x_2) = x_1 + x_2 + 2x_1x_2,\] where \(\mathbb{E}X_1 = \mathbb{E}X_2 = 0\) and \(\mathbb{Var}X_1 = \mathbb{Var}X_2 = 1\).

It can be shown that SHAP value for the first feature is \[\phi_1(x_1, x_2) = x_1 - \mathbb{E}[X_1] + x_1x_2 - \mathbb{E}[X_1X_2] + x_1\mathbb{E}[X_2] - x_2\mathbb{E}[X_1] = x_1 + x_1 x_2 - \mathrm{corr}(X_1, X_2).\]

If \(\mathrm{corr}(X_1, X_2) = 0.3\), then for observation with \((x_1, x_2) = (1, -0.7)\), SHAP value for the first feature is \(\phi_1(1, -0.7) = 0\).

WHY? The main effect contribution and interaction contribution cancel each other out.

WHAT TO DO? Decompose SHAP value \(\phi_1\) into main and interaction contributions.

SHAP values vs. functional decomposition

SHAP values and functional decomposition for XGBoost model of \(m(x_1, x_2)\) function.

Main results

Contributions

Introducing global¹ explanation procedure.
New interpretation of SHAP values (not connected with game theory).
Implementing algorithm for tree-based models (glex R package).

What can be done with this new explanation method?

Of course visualizations (for one, two and even three-dimensional contributions).
Decomposition of simple SHAP values.
Aggregation into feature importance values.
Detecting and reducing bias in models.

Functional decomposition

The functional decomposition of \(\widehat{m}(x)\): \[\begin{align*} \widehat{m}(x) &= \widehat{m}_0 + \sum_{k=1}^{d}\widehat{m}_k(x_k) + \sum_{k\neq l}\widehat{m}_{k,l}(x_k, x_l) + \ldots + \widehat{m}_{1, \ldots, d}(x) \\ &= \sum_{S \subseteq [d]}\widehat{m}_S(x_S) \end{align*}\]

Without identification constraints, it has many solutions.
Added constraints – called marginal identification: \[ \forall S \subseteq [d] \quad\; \sum_{T \cap S \neq \emptyset} \mathbb{E}_{X_{S}}[\widehat{m}_T(x_T)] = 0 \]
More intuitively, it is equivalent to: \[ \forall S \subseteq [d] \quad\; \sum_{T} \mathbb{E}_{X_{S}}[\widehat{m}_T(x_T)] = \sum_{T \cap S = \emptyset} \widehat{m}_T(x_T)\]

There exists an unique solution for this problem.

(Some math skipped here.)

Connection with interventional SHAP values

Interventional SHAP values are obtained via the well-known Shapley formula from the value function: \[v(x^*, S) = \mathbb{E}_{X_{-S}} [\widehat{m}(x_{S}, x_{-S}) | X_S = x^{*}_S].\]
The interventional SHAP values are weighted averages of the corresponding components from proposed functional decomposition. (Note: Local SHAP values can be described by the components of global explanation!)
The relation is quite simple: \[\phi_k(x) = \widehat{m}_k(x_k) + \frac12 \sum_j \widehat{m}_{k,j}(x_k, x_j) + \ldots + \frac1d \widehat{m}_{1,\ldots,d}(x).\]

Side note

Why to emphasize interventional?
- Bordt and von Luxburg in From Shapley Values to Generalized Additive Models and back show that for every subset-compliant¹ value function used for estimation of Shapley values, there is a corresponding functional decomposition (and vice-versa).
- Such a correspondence has been already described also for observational (conditional) SHAP value function.
They also propose \(n\)-Shapley Values – parametrized by \(n\) family of algorithms that explain predictions with interactions terms up to order \(n\). It extends standard Shapley Values and Shapley Interaction Values.

Connection with PDP

Partial Dependence Plots can be described in terms of proposed global explanation: \[\begin{align*} PDP_S(x_S) &= \mathbb{E}_{X_{-S}}[\widehat{m}(x)|X_S=x_S] \\ &= \sum_{U \subseteq S} \widehat{m}_U(x_U). \end{align*}\]

For one-dimensional case: \[ PDP_k(x_k) = \widehat{m}_0 + \widehat{m}_k(x_k).\]

De-biasing application

Proposed global explanation allows for de-biasing via post-hoc feature removal.

If \(U\) is the set of protected features and \(V = [d] \setminus U\), de-biased version of model is: \[ \widetilde{m}(x_{-U}) = \sum_{S \subseteq V} \widehat{m}_S(x_S).\]

New perspective on feature importance

In feature importance calculated based on SHAP values, contributions from interactions and main effects can cancel each other out.

Having functional decomposition, we can consider:

\(\mathrm{Importance}(X_k) = \mathbb{E}\left[\sum_{S: \, k \in S} \frac{1}{|S|} |\widehat{m}_S(X_S)|\right]\),
extended definition of feature importance (for interactions).

Experiments

Global explanation results

Feature importance results

Also for the function \(m(x) = x_1 + x_3 + x_2x_3 - 2 x_2 x_3 x_4\).

De-biasing results

Adult dataset and simulated data (in both gender being a protected feature)
In simulated data: \[salary = working \; hours \\ + 20 \cdot \mathbf{1}\{gender=male\}\] and working hours greater for men.

Takeaways

Interventional SHAP \(\iff\) functional decomposition with marginal identification constraints.
Dealing with misleading explanations via taking into account interaction effects.
De-biasing application.

What’s next?

Finding another correspondences (connected to another causal structures).
Finding new algorithms for estimating components of the decomposition.
(Inspirational remark) Shapley formula is a powerful tool. Relevant and smart definition of value function can lead to interesting and valuable results.